package com.hanxiaozhang.no10leetcode.string;

import java.util.Stack;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * <p>
 * 给定一个仅包含'(', ')', '{', '}', '[', ']'这几个特殊符号的字符串，判断输入是否合法
 * 合法条件：括号一开一闭相对应 括号开闭顺序要一致
 * <p>
 * 背方法2
 * 思路：
 * 1.使用栈结构
 * 2.循环遇到左符号，在栈插入其对应的右符号
 * 3.循环遇到右符号，弹出栈中符号，判断是否相等，相等继续循环，不相等，返回false
 * 4.最后判断栈是否为空。
 *
 * @author hanxinghua
 * @create 2024/1/9
 * @since 1.0.0
 */
public class No20ValidParentheses {

    public static void main(String[] args) {

        String s = "((()))";

        System.out.println(method1(s));
        System.out.println(method1_optimize(s));
        System.out.println(method2(s));


    }

    /**
     * 方法2
     * <p>
     * 思路：
     * 1.循环遇到左符号，在栈插入其对应的右符号
     * 2.循环遇到右符号，弹出栈中符号，判断是否相等，相等继续循环，不相等，返回false
     * 3.最后判断栈是否为空。
     *
     * @param s
     * @return
     */
    public static boolean method2(String s) {

        String[] arrays = s.split("");
        Stack<String> stack = new Stack();
        for (int i = 0; i < arrays.length; i++) {
            String array = arrays[i];
            if (array.equals("(")) {
                stack.push(")");
            } else if (array.equals("{")) {
                stack.push("}");
            } else if (array.equals("[")) {
                stack.push("]");
                // 弹出元素，判断是否与当前元素相等
            } else if (!stack.isEmpty() && !stack.pop().equals(array)) {
                return false;
            }

        }
        return stack.isEmpty();
    }


    /**
     * 方法1
     * <p>
     * 有点笨
     * 思路：左符号先插入栈，然后再判断右符号与栈顶元素是否形成一对，一对弹出。
     * 最后判断栈内是否有元素。
     *
     * @param s
     * @return
     */
    private static boolean method1(String s) {
        String[] arrays = s.split("");
        Stack<String> stack = new Stack();

        for (int i = 0; i < arrays.length; i++) {
            String array = arrays[i];
            boolean flag = false;

            if (!stack.isEmpty()) {
                if ((array.equals(")") && stack.peek().equals("(")) ||
                        (array.equals("}") && stack.peek().equals("{")) ||
                        (array.equals("]") && stack.peek().equals("["))
                ) {
                    stack.pop();
                } else {
                    flag = true;
                }
            } else {
                flag = true;
            }

            if (flag) {
                stack.push(array);
                flag = false;
            }
        }

        return stack.isEmpty();
    }

    private static boolean method1_optimize(String s) {
        String[] arrays = s.split("");
        Stack<String> stack = new Stack();

        for (int i = 0; i < arrays.length; i++) {
            String array = arrays[i];
            boolean pushFlag = true;
            if (!stack.isEmpty()) {
                if ((array.equals(")") && stack.peek().equals("(")) ||
                        (array.equals("}") && stack.peek().equals("{")) ||
                        (array.equals("]") && stack.peek().equals("["))
                ) {
                    stack.pop();
                    pushFlag = false;
                }
            }
            if (pushFlag) {
                stack.push(array);
            }
        }
        return stack.isEmpty();
    }

}
